use std::sync::{LazyLock, Mutex};

static mut FIBOS_RE: LazyLock<Mutex<Vec<u32>>> = LazyLock::new(|| Mutex::new(vec![0, 1]));
static mut SUM_ODD: LazyLock<Mutex<Vec<u32>>> = LazyLock::new(|| Mutex::new(vec![0, 1]));
pub fn odd_fibnacci_sum(threshold: u32) -> u32 {
    let mut global = unsafe { FIBOS_RE.lock().unwrap() };
    while &threshold > global.last().unwrap() {
        let last = global.len() - 1;
        let new = global[last] + global[last - 1];
        global.push(new);
        let mut sum = unsafe { SUM_ODD.lock().unwrap() };
        let sum_last = sum.last().unwrap().clone();
        if new % 2 == 1 {
            sum.push(sum_last + new);
        } else {
            sum.push(sum_last);
        }
    }
    let sum = unsafe { SUM_ODD.lock().unwrap() };
    sum[find_max_less_than(threshold, &global).unwrap()]
}

pub fn find_max_less_than(target: u32, arr: &[u32]) -> Option<usize> {
    if arr.is_empty() || target <= arr[0] {
        return None;
    }

    let mut low = 0;
    let mut high = arr.len() - 1;
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid] < target {
            if mid == arr.len() - 1 || arr[mid + 1] >= target {
                return Some(mid);
            }
            low = mid + 1;
        } else {
            if mid == 0 {
                return None;
            }
            high = mid - 1;
        }
    }
    None
}
